#排排坐 分糖果

#题目

有 n 个小朋友围成一圈；老师给每个小朋友随机发放偶数个糖果，然后进行下面的游戏：

1. 每个小朋友把自己的糖果分一半给左手边的孩子
2. 老师给拥有糖果数量为奇数的小朋友补发一颗糖果使其变成偶数

重复上述步骤，直到所有小朋友的糖果数量都相同。

求老师一共需要补发多少颗糖果？

#分析

这个问题容易出错的地方在于 小朋友把自己的糖果分一半给左手边的孩子 这个行为是并行的。

如果简单的将数组元素的值减小一半加到后一个元素上，就会变成 B 收到 A 给他的糖果后，再分一半给 C。

这样就导致给多了，需要在接收前面孩子的糖果直接 缓存 自己的糖果数量。

#解答

-- 随机生成初始状态
local N = 10
local array = {}

for i = 1, N do
    array[i] = math.random(0, 9) * 2
end

-- 打印函数
local function print_array(prefix, arr)
    io.write(prefix)
    io.write(" [")
    for i = 1, #arr do
        io.write(arr[i])
        if i < #arr then io.write(", ") end
    end
    print("]")
end

print_array("初始状态：", array)

-- 补发糖果数
local count = 0

-- 判断是否所有值相同
local function all_equal(arr)
    local first = arr[1]
    for i = 2, #arr do
        if arr[i] ~= first then
            return false
        end
    end
    return true
end

-- 循环直到所有人一样多
while not all_equal(array) do
    -- 拷贝
    local shadow = {}
    for i = 1, N do
        shadow[i] = array[i]
    end

    -- 前一个人把一半糖果给后一个人
    for i = 2, N do
        array[i] = math.floor(shadow[i] / 2) + math.floor(shadow[i - 1] / 2)
    end

    -- 最后一个给第一个
    array[1] = math.floor(shadow[1] / 2) + math.floor(shadow[N] / 2)

    print_array("向左分享：", array)

    -- 对奇数补发糖果
    for i = 1, N do
        if array[i] % 2 == 1 then
            array[i] = array[i] + 1
            count = count + 1
        end
    end

    print_array("老师补发：", array)
end

-- 打印结果
print("总共补发：", count)

运行代码
>>> Establishing WebAssembly Runtime. 
>>> Standby. 
Powered by Shift.